/* Copyright (c) 2006-2012, DNSPod Inc.
 * All rights reserved.

 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of the FreeBSD Project.
 */
 

#include "datas.h"


//!!!!!!!!!!!!!could NOT used in multithread env!!!!!!!!!!!!!!!!!!


//--------------------red black tree---------
static void
left_rotate( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     rbnode *tmp = p_rbnode->right;
    p_rbnode->right = tmp->left;
    if (tmp->left != &p_rbtree->nil)
        tmp->left->parent = p_rbnode;
    tmp->parent = p_rbnode->parent;
    if (p_rbnode->parent == &p_rbtree->nil)
        p_rbtree->root = tmp;
    else if (p_rbnode == p_rbnode->parent->left)
        p_rbnode->parent->left = tmp;
    else
        p_rbnode->parent->right = tmp;
    tmp->left = p_rbnode;
    p_rbnode->parent = tmp;
}


static void
right_rotate( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     rbnode *tmp = p_rbnode->left;
    p_rbnode->left = tmp->right;
    if (tmp->right != &p_rbtree->nil)
        tmp->right->parent = p_rbnode;
    tmp->parent = p_rbnode->parent;
    if (p_rbnode->parent == &p_rbtree->nil)
        p_rbtree->root = tmp;
    else if (p_rbnode == p_rbnode->parent->left)
        p_rbnode->parent->left = tmp;
    else
        p_rbnode->parent->right = tmp;
    tmp->right = p_rbnode;
    p_rbnode->parent = tmp;
}


static void
insert_fixup( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     rbnode *tmp;
    while (p_rbnode->parent->color == RED) {
        if (p_rbnode->parent == p_rbnode->parent->parent->left) {
            tmp = p_rbnode->parent->parent->right;
            if (tmp->color == RED) {
                p_rbnode->parent->color = tmp->color = BLACK;
                p_rbnode->parent->parent->color = RED;
                p_rbnode = p_rbnode->parent->parent;
            } else {
                if (p_rbnode == p_rbnode->parent->right) {
                    p_rbnode = p_rbnode->parent;
                    left_rotate(p_rbtree, p_rbnode);
                }
                p_rbnode->parent->color = BLACK;
                p_rbnode->parent->parent->color = RED;
                right_rotate(p_rbtree, p_rbnode->parent->parent);
            }
        } else {
            tmp = p_rbnode->parent->parent->left;
            if (tmp->color == RED) {
                p_rbnode->parent->color = tmp->color = BLACK;
                p_rbnode->parent->parent->color = RED;
                p_rbnode = p_rbnode->parent->parent;
            } else {
                if (p_rbnode == p_rbnode->parent->left) {
                    p_rbnode = p_rbnode->parent;
                    right_rotate(p_rbtree, p_rbnode);
                }
                p_rbnode->parent->color = BLACK;
                p_rbnode->parent->parent->color = RED;
                left_rotate(p_rbtree, p_rbnode->parent->parent);
            }
        }
    }
    p_rbtree->root->color = BLACK;
}


//find_node and delete_node are not safe
//delete node may return NULL.
 rbnode *
find_node( rbtree *p_rbtree, void *key)
{
     rbnode *p_rbnode = &p_rbtree->nil;
    int i;
    //pthread_mutex_lock(&(rbt->lock));
    p_rbnode = p_rbtree->root;
    while (p_rbnode != &p_rbtree->nil) {
        i = (p_rbtree->c) (p_rbnode->key, key, p_rbtree->argv);
        if (i > 0)
            p_rbnode = p_rbnode->left;
        if (i < 0)
            p_rbnode = p_rbnode->right;
        if (p_rbnode == &p_rbtree->nil)
            break;              //return null
        if (i == 0) {
            //pthread_mutex_unlock(&(rbt->lock));
            return p_rbnode;
        }
    }
    //pthread_mutex_unlock(&(rbt->lock));
    return NULL;
}


int
insert_node( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     rbnode *tmp = &p_rbtree->nil, *itor = p_rbtree->root;
     rbnode *p_node = malloc(sizeof( rbnode));
    if (p_node == NULL)
        return -1;
    *p_node = *p_rbnode;
    //pthread_mutex_lock(&(rbt->lock));
    while (itor != &p_rbtree->nil) {
        tmp = itor;
        if ((p_rbtree->c) (itor->key, p_node->key, p_rbtree->argv) > 0)
            itor = itor->left;
        else
            itor = itor->right;
    }
    p_node->parent = tmp;
    if (tmp == &p_rbtree->nil)
        p_rbtree->root = p_node;
    else {
        if ((p_rbtree->c) (tmp->key, p_node->key, p_rbtree->argv) > 0)
            tmp->left = p_node;
        else
            tmp->right = p_node;
    }
    p_node->left = p_node->right = &p_rbtree->nil;
    p_node->color = RED;
    insert_fixup(p_rbtree, p_node);
    p_rbtree->size++;
    //pthread_mutex_unlock(&(rbt->lock));
    /* printf("\t\t\t\t\t\t\tafter insert, rbt size: %d\n", get_rbt_size(rbt)); */
    return 0;
}


static  rbnode *
rbt_successor( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     rbnode *min = &p_rbtree->nil;
    if (p_rbnode->right != &p_rbtree->nil) {
        min = p_rbnode->right;
        while (min->left != &p_rbtree->nil)
            min = min->left;
        return min;
    }
    min = p_rbnode->parent;
    while ((min != &p_rbtree->nil) && (p_rbnode == min->right)) {
        p_rbnode = min;
        min = min->parent;
    }
    return min;
}


static void
delete_fixup( rbtree *p_rbtree,  rbnode *p_node)
{
     rbnode *tmp = &p_rbtree->nil;
    while (p_node != p_rbtree->root && p_node->color == BLACK)
        if (p_node == p_node->parent->left) {
            tmp = p_node->parent->right;
            if (tmp->color == RED) {
                tmp->color = BLACK;
                p_node->parent->color = RED;
                left_rotate(p_rbtree, p_node->parent);
                tmp = p_node->parent->right;
            }
            if (tmp->left->color == BLACK && tmp->right->color == BLACK) {
                tmp->color = RED;
                p_node = p_node->parent;
            } else {
                if (tmp->right->color == BLACK) {
                    tmp->left->color = BLACK;
                    tmp->color = RED;
                    right_rotate(p_rbtree, tmp);
                    tmp = p_node->parent->right;
                }
                tmp->color = p_node->parent->color;
                p_node->parent->color = BLACK;
                tmp->right->color = BLACK;
                left_rotate(p_rbtree, p_node->parent);
                p_node = p_rbtree->root; //end while
            }
        } else {
            tmp = p_node->parent->left;
            if (tmp->color == RED) {
                tmp->color = BLACK;
                p_node->parent->color = RED;
                right_rotate(p_rbtree, p_node->parent);
                tmp = p_node->parent->left;
            }
            if (tmp->right->color == BLACK && tmp->left->color == BLACK) {
                tmp->color = RED;
                p_node = p_node->parent;
            } else {
                if (tmp->left->color == BLACK) {
                    tmp->right->color = BLACK;
                    tmp->color = RED;
                    left_rotate(p_rbtree, tmp);
                    tmp = p_node->parent->left;
                }
                tmp->color = p_node->parent->color;
                p_node->parent->color = BLACK;
                tmp->left->color = BLACK;
                right_rotate(p_rbtree, p_node->parent);
                p_node = p_rbtree->root; //end while
            }
        }
    p_node->color = BLACK;
}


 rbnode *
min_node( rbtree *p_rbtree)
{
     rbnode *tmp, *ret;
    //pthread_mutex_lock(&(rbt->lock));
    tmp = p_rbtree->root;
    ret = &p_rbtree->nil;
    if (tmp == &p_rbtree->nil) {
        //pthread_mutex_unlock(&(rbt->lock));
        return NULL;
    }
    while (tmp != &p_rbtree->nil) {
        ret = tmp;
        tmp = tmp->left;
    }
    if (ret == &p_rbtree->nil) {
        //pthread_mutex_unlock(&(rbt->lock));
        return NULL;
    }
    //pthread_mutex_unlock(&(rbt->lock));
    return ret;
}

 
//free node, return val
void *
delete_node( rbtree *p_rbtree,  rbnode *p_rbnode)
{
     ttlnode *p_ttlnode = NULL;
     rbnode *ret = p_rbnode;
     rbnode *tmp, *itor;
    if (p_rbnode == NULL || p_rbtree == NULL)
        return NULL;
    p_ttlnode = p_rbnode->key;
    /* printf("delete node ttl: %d ", val->exp); */
    /* dbg_print_td(val->data); */
    //pthread_mutex_lock(&(rbt->lock));
    if (p_rbnode->left == &p_rbtree->nil || p_rbnode->right == &p_rbtree->nil)
        tmp = p_rbnode;
    else
        tmp = rbt_successor(p_rbtree, p_rbnode);
    if (tmp->left != &p_rbtree->nil)
        itor = tmp->left;
    else
        itor = tmp->right;
    itor->parent = tmp->parent;
    if (tmp->parent == &p_rbtree->nil)
        p_rbtree->root = itor;
    else {
        if (tmp == tmp->parent->left)
            tmp->parent->left = itor;
        else
            tmp->parent->right = itor;
    }
    if (tmp != itor)
        p_rbnode->key = tmp->key;
    if (tmp->color == BLACK)
        delete_fixup(p_rbtree, itor);
    if (ret == NULL)
        printf("ret is null\n");
    free(tmp);
    p_rbtree->size--;
    //pthread_mutex_unlock(&(rbt->lock));
    /* printf("\t\t\t\t\t\t\tafter delete, rbt size: %d\n", get_rbt_size(rbt)); */
    return p_ttlnode;
}


 rbtree *
create_rbtree(comprbt * compare_func, void *argv)
{
     rbtree *p_rbtree = malloc(sizeof( rbtree));
    if (p_rbtree == NULL)
        return NULL;
    p_rbtree->argv = argv;
    p_rbtree->c = compare_func;
    p_rbtree->size = 0;
    pthread_spin_init(&p_rbtree->lock, 0);
    p_rbtree->nil.parent = &(p_rbtree->nil);
    p_rbtree->nil.left = &(p_rbtree->nil);
    p_rbtree->nil.right = &(p_rbtree->nil);
    p_rbtree->nil.color = BLACK;
    p_rbtree->nil.key = NULL;
    p_rbtree->root = &p_rbtree->nil;
    return p_rbtree;
}


uint
get_rbt_size( rbtree * p_rbtree)
{
    return p_rbtree->size;
}


int
free_rbtree( rbtree *p_rbtree)
{
    if (get_rbt_size(p_rbtree) > 0)
        return -1;
    free(p_rbtree);
    return 0;
}


//---------------rbtree debug------------------------------------//
int
rbtree_test(void)
{
    int i, j, len, slice, ret;
     rbnode node, *pn = NULL;
     ttlnode *tn = NULL;
     rbtree *rbt = NULL;
    rbt = create_rbtree(rbt_comp_ttl_gt, NULL);
    if (rbt == NULL)
        dns_error(0, "create rbtree");
    node = rbt->nil;            //nil
    slice = 8000000;
    //for(i = 0;i < n;i ++)
    //{
    for (j = 0; j < slice; j++) {
        len = random() % 30;
        tn = malloc(sizeof( ttlnode) + len);
        if (tn == NULL)
            printf("oom\n");
        tn->exp = j;
        for (i = 0; i < len; i++)
            tn->data[i] = 'a' + i;
        node.key = tn;
        ret = insert_node(rbt, &node);
        if (ret != 0)
            printf("insert error\n");
    }
    printf("insert all\n");
    sleep(2);
    for (j = 0; j < slice; j++) {
        pn = min_node(rbt);
        if (pn != NULL) {
            tn = delete_node(rbt, pn);
            free(tn);
        } else
            printf("error\n");
    }
    printf("delete all\n");
    sleep(5);
    //}
    if (free_rbtree(rbt) != 0)
        dns_error(0, "free");
    //get_time_usage(&tv,0);
    return 0;
}
